// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type FrequencyStack struct {
	freq    map[int]int
	group   map[int][]int
	maxfreq int
}

func NewFrequencyStack() FrequencyStack {
	hash := make(map[int]int)
	maxHash := make(map[int][]int)
	return FrequencyStack{freq: hash, group: maxHash}
}

func (fs *FrequencyStack) Push(x int) {
	if _, ok := fs.freq[x]; ok {
		fs.freq[x]++
	} else {
		fs.freq[x] = 1
	}
	f := fs.freq[x]
	if f > fs.maxfreq {
		fs.maxfreq = f
	}

	fs.group[f] = append(fs.group[f], x)
}

func (fs *FrequencyStack) Pop() int {
	tmp := fs.group[fs.maxfreq]
	x := tmp[len(tmp)-1]
	fs.group[fs.maxfreq] = fs.group[fs.maxfreq][:len(fs.group[fs.maxfreq])-1]
	fs.freq[x]--
	if len(fs.group[fs.maxfreq]) == 0 {
		fs.maxfreq--
	}
	return x
}

func main() {
	i := 8
	j := 16
	obj := NewFrequencyStack()
	obj.Push(i)
	obj.Push(j)
	ret1 := obj.Pop()
	ret2 := obj.Pop()
	fmt.Println(ret1)
	fmt.Println(ret2)
}

//$ go run interview3-1.go
//16
//8
